package com.algorithms.techniques.graph;

import java.util.Arrays;

public class DepthFirstSearch
{
   enum COLOUR {WHITE,GRAY,BLACK};
   int nodes;
   COLOUR[] colour  =null;
   int[] dis;
   int[] fin;
   int[][] graphMatrix =null;
   int time;
   public DepthFirstSearch(int[][] iGraphMatrix)
   {
	   graphMatrix=iGraphMatrix;
	   colour = new COLOUR[graphMatrix.length];
	   dis =new int[graphMatrix.length];
	   fin =new int[graphMatrix.length];
   }
	
   public void dfs()
   {
	   for (int node=0 ;node <graphMatrix.length ;node++)
	   {
		   colour[node]=COLOUR.WHITE;
	   }
	   time=0;
	   for (int node=0 ;node <graphMatrix.length ;node++)
	   {
		   if(colour[node]==COLOUR.WHITE)
			   dfsVisit(node);
	   }
   }
   
   private void dfsVisit(int cNode)
   {
	   colour[cNode]=COLOUR.GRAY;
	   time=time+1;
	   dis[cNode]=time;
	   for(int i=0;i<graphMatrix.length;i++)
	   {
		   if(graphMatrix[cNode][i]==1 && colour[i].equals(COLOUR.WHITE))
			   dfsVisit(i);
	   }
	   colour[cNode]=COLOUR.BLACK;
	   time=time+1;
	   fin[cNode]=time;
   }

    public void topologicalSort()
    {
    	Arrays.sort(fin);
    	System.out.println("");
		
    }
	public int[] getDis() {
		return dis;
	}
	
	public void setDis(int[] dis) {
		this.dis = dis;
	}
	
	public int[] getFin() {
		return fin;
	}
	
	public void setFin(int[] fin) {
		this.fin = fin;
	}
   
}
